package Hot_100;

import org.junit.Test;

/*
    79. 单词搜索
    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
    如果 word 存在于网格中，返回 true ；否则，返回 false 。
    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
    同一个单元格内的字母不允许被重复使用。
* */
public class T79_exist {
    int[][] dirt = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; //上 下 左 右

    @Test
    public void test() {
        char[][] borad = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        char[][] borad = {{'a', 'b', 'c'}, {'a', 'e', 'd'}, {'a', 'f', 'g'}};
//        char[][] borad = {{'a', 'a'}};
        String word = "ABCB";
        System.out.println(exist(borad, word));
    }

    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] flag = new boolean[n][m];
        if (n == 1 && m == 1 && word.length() == 1) {
            if (word.charAt(0) == board[0][0]) {
                return true;
            }else {
                return false;
            }
        }


        for (int i = 0; i < n; i++) {   //从任意一个起点出发
            for (int j = 0; j < m; j++) {
                flag[i][j] = true;  //递归里面没有对第一个元素进行标记，所以这里要先标记
                boolean isExist=dfs(board, flag, word,  n, m, i, j, 0);
                if (isExist) {
                    return true;
                }
                flag[i][j] = false;
            }
        }
        return false;
    }

    boolean dfs(char[][] board, boolean[][] flag, String word, int n, int m, int x, int y,int count) {
        if (word.charAt(count) != board[x][y]) { //如果指针指向的字符和word对应的字符不相等
            return false;
        }

        if (count == word.length()-1) {
            return true;
        }

        boolean sign;
        for (int i = 0; i < 4; i++) {
            int nx = x + dirt[i][0];
            int ny = y + dirt[i][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !flag[nx][ny]) { //如果向某个指定方向移动不会越界
                flag[nx][ny] = true;
                sign = dfs(board, flag, word,  n, m, nx, ny, count + 1);
                if (sign) {
                    return true;
                }
                flag[nx][ny] = false;
            }
        }
        return false;
    }
}
